package com.programmercarl.dp;

/**
 * https://leetcode.cn/problems/partition-equal-subset-sum/description/
 * 416. 分割等和子集
 *
 * @author yulongtian
 * @create 2025-02-16 22:22
 */
public class Test08_01 {
    public static void main(String[] args) {
        Test08_01 test0801 = new Test08_01();
        System.out.println(test0801.canPartition(new int[]{1, 2, 3, 5}));
    }

    /**
     * 尝试使用回溯法
     * 正确，但超出时间限制
     *
     * @param nums
     * @return
     */
    boolean flag = false;

    public boolean canPartition(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return false;
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
        }
        if (sum % 2 != 0) {
            return false;
        }
        backTracking(nums, sum, 0, 0);

        return flag;
    }


    public void backTracking(int[] nums, int totalSum, int tempSum, int startIndex) {
        if (totalSum == tempSum * 2) {
            flag = true;
            return;
        }
        if (flag) {
            return;
        }
        for (int i = startIndex; i < nums.length; i++) {
            tempSum += nums[i];
            backTracking(nums, totalSum, tempSum, i + 1);
            tempSum -= nums[i];
        }
    }

}
